package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-05-05 14:09
 */
public class LongestRepeatingSubArray {
    /**LeetCode 718
     * 寻找最长重复子串：五部曲：1.dp[i][j]一个序列1以i-1 和序列2以j-1 为结尾的数组的重复子串  递推公式：dp[i][j]=dp[i-1][j-1]+1(然后最后遍历
     * 找最大值) 初始化：考虑到i 和 j仅和前面的数组有关，所以第一行和第一列无效 ，均初始化为0 遍历顺序：行和列均从0开始
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int findLength(int[] nums1, int[] nums2) {
        //创建dp数组
        int[][]dp=new int[nums1.length+1][nums2.length+1];
        //进行遍历
        //设置返回值
        int res=0;
        for(int i=1;i<=nums1.length;++i){
            for(int j=1;j<=nums2.length;++j){
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                if(dp[i][j]>res){
                    res=dp[i][j];
                }
            }

        }
        return res;
    }
}
